// 最坏情况O(n^2), 最好情况: 未被证明
export default function shellSort(arr: number[]): number[] {
  const n = arr.length;

  let gap = Math.floor(n / 2);

  // 改变步长过程
  while (gap > 0) {
    for (let i = gap; i < n; i++) {
      let j = i;
      const num = arr[i];
      while (j >= gap - 1 && arr[j - gap] > num) {
        arr[j] = arr[j - gap];
        j = j - gap;
      }
      arr[j] = num;
    }

    gap = Math.floor(gap / 2);
  }

  return arr;
}

console.log(shellSort([12, 232, 43, 12, 423, 1, 2, 3]));
